package algo.sort;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class QuickSort<T extends Comparable<? super T>> extends Sort<T>{

    private static int minLength = 47;

    @Override
    public void sort(T[] nums) {
        if (nums.length > minLength) {
            shuffle(nums);
            toSort(nums, 0, nums.length - 1);
        } else {
           new Insertion<T>().sort(nums);
        }

    }
    protected void toSort(T[] nums, int left, int right) {
        if (left >= right) return;

        int j = partition(nums, left, right);
        toSort(nums, left, j-1);
        toSort(nums, j+1, right);
    }

    protected void toSortDesc(T[] nums, int left, int right) {
        if (left >= right) return;

        int j = partitionDesc(nums, left, right);
        toSortDesc(nums, left, j-1);
        toSortDesc(nums, j+1, right);
    }

    private int partition(T[] nums, int left, int right) {
        int i=left, j=right+1;
        T v = nums[left];
        while (true) {
            while (less(nums[++i], v) && i != right);
            while (less(v, nums[--j]) && j != left);

            if (i >= j) break;

            swap(nums, i, j);
        }
        swap(nums, left, j);
        return j;
    }

    private int partitionDesc(T[] nums, int left, int right) {
        int i=left, j=right+1;
        T v = nums[left];
        while (true) {
            while (greater(nums[++i], v) && i != right);
            while (greater(v, nums[--j]) && j != left);

            if (i >= j) break;

            swap(nums, i, j);
        }
        swap(nums, left, j);
        return j;
    }

    @Override
    public void sortDesc(T[] nums) {
        if (nums.length > minLength) {
            shuffle(nums);
            toSortDesc(nums, 0, nums.length - 1);
        } else {
            new Insertion<T>().sortDesc(nums);
        }
    }

    private void shuffle(T[] nums) {
        List<Comparable> list = Arrays.asList(nums);
        Collections.shuffle(list);
        list.toArray(nums);
    }

    public T selectKthBig(T[] nums, int k) {
        --k;
        if (k<0) k=0;

        int left = 0,  right = nums.length-1;

        while (left < right) {
            int j = partitionDesc(nums, left, right);

            if (j == k) {
                return nums[k];
            } else if (j > k) {
                right = j - 1;
            } else {
                left = j + 1;
            }
        }

        return nums[k];
    }
    public T selectKthSmall(T[] nums, int k) {
        --k;
        if (k<0) k=0;

        int left = 0,  right = nums.length-1;

        while (left < right) {
            int j = partition(nums, left, right);

            if (j == k) {
                return nums[k];
            } else if (j > k) {
                right = j - 1;
            } else {
                left = j + 1;
            }
        }

        return nums[k];
    }
}
